package a08_回溯算法;

import java.util.Arrays;

/**
 * 两层for循环遍历棋盘
 * 递归用来判断某个数放在某个位置是否合适
 *
 *
 * @author flyduck
 * @since 2025/1/6
 */
public class a21_解数独 {

    public static void main(String[] args) {
        a21_解数独 test = new a21_解数独();
        char[][] board = new char[9][9];
        board[0] = new char[]{'5','3','.','.','7','.','.','.','.'};
        board[1] = new char[]{'6','.','.','1','9','5','.','.','.'};
        board[2] = new char[]{'.','9','8','.','.','.','.','6','.'};
        board[3] = new char[]{'8','.','.','.','6','.','.','.','3'};
        board[4] = new char[]{'4','.','.','8','.','3','.','.','1'};
        board[5] = new char[]{'7','.','.','.','2','.','.','.','6'};
        board[6] = new char[]{'.','6','.','.','.','.','2','8','.'};
        board[7] = new char[]{'.','.','.','4','1','9','.','.','5'};
        board[8] = new char[]{'.','.','.','.','8','.','.','7','9'};
        System.out.println("开始");
        test.solveSudoku(board);
        for (int i = 0; i < board.length; i++) {
            System.out.println(Arrays.toString(board[i]));
        }

    }


    public void solveSudoku(char[][] board) {
        traversal(board);
    }

    private boolean traversal(char[][] board){
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[i].length; j++) {
                if(board[i][j] == '.'){
                    for(char k = '1';k <= '9';k++){
                        if (isValid(board, board.length, i, j, k)) {
                            board[i][j] = k;
                            boolean result = traversal(board);//假设这次执行的最后一个格子，执行完就必须返回了，不能再执行board[i][j] = '.'了
                            if (result) {
                                return true;
                            }
                            board[i][j] = '.';
                        }
                    }
                    //九个数如果都不行，要回溯了。让调用走board[i][j] = '.';
                    System.out.println("return");
                    return false;
                }
            }
        }
        return true;
    }

    private boolean isValid(char[][] board,int n, int rowIdx, int colIdx, char target) {
        for (int i = 0; i < n; i++) {
            if(i == rowIdx){
                continue;
            }
            if (board[i][colIdx] == target) {
                return false;
            }
        }
        for (int i = 0; i < n; i++) {
            if(i == colIdx){
                continue;
            }
            if (board[rowIdx][i] == target) {
                return false;
            }
        }
        for (int i = (rowIdx / 3) * 3; i < (rowIdx / 3) * 3 + 3; i++) {
            for (int j = (colIdx / 3) * 3; j < (colIdx / 3) * 3 + 3; j++) {
                if(i == rowIdx && j == colIdx){
                    continue;
                }else {
                    if(board[i][j] == target){
                        return false;
                    }
                }
            }
        }
        return true;

    }
}
